# -*- coding: utf-8 -*-
"""
 Author：Zhaoqiang Shen
 Date：2018.03.13
《算法导论》（中文第三版）Binary-sum
"""
from __future__ import print_function
from array import array

def binary_sum(A, B):
    "Ex 2.1-4"
    C = array('i', [0]*(len(A)+1))
    for i in reversed(range(len(A))):
        temp = C[i+1] + A[i] + B[i]
        C[i] = temp // 2
        C[i+1] = temp % 2
    return C

if __name__ == '__main__':
    a = array('i', [1, 0, 1, 1])
    b = array('i', [0, 1, 0, 1])
    print('  A:  ', ''.join(str(v) for v in a))
    print('  B:  ', ''.join(str(v) for v in b))

    c = binary_sum(a, b)
    print('A+B: ', ''.join(str(v) for v in c))
